3614. 含特殊操作的字符串处理 II

3614. Process String with Special Operations II

🧩 核心思路

模型：反向模拟（逆推）。

正向构造字符串不可行——# 每次翻倍长度，指数级增长。改为正向记录每步长度，再从目标位置 k 倒推，还原该位置的字符来源。

🔧 解题步骤

1. 正向记录长度：遍历操作串 s，维护当前字符串长度 len（用 BigInt），每步存入数组 lens。
2. 越界检查：若 k ≥ 最终长度，直接返回 '.'。
3. 逆推位置：从末尾向前遍历操作串，根据当前操作类型反向修正 pos：
   • 字母：若 pos === prevLen，说明 pos 恰好是该字母新增的位置，返回该字符。
   • #：pos %= prevLen（翻倍后两个副本映射到同一源位置）。
   • %：pos = prevLen - 1 - pos（反转对称映射）。
   • *：pos 不变（退格只影响末尾，其他位置不受影响）。
4. 遍历结束仍未返回 → 返回 '.'。

⚠️ 关键点 / 易错点

• 长度会指数增长，必须用 BigInt，Number 会溢出。
• pos === prevLen 的判断条件（不是 pos === currLen - 1n）——字母新增的位置正好是 prevLen。
• # 翻倍时 pos %= prevLen 利用了取模将后半段映射回前半段。
• % 反转：pos = prevLen - 1n - pos，注意是 prevLen - 1n 不是 currLen - 1n。
• * 退格操作：只删除最后字符，pos 索引不变（除非 pos 指向被删字符——但 pos 有效时不会指向它）。

🧪 复杂度

• 时间复杂度：O(N)，N 为操作串长度，正反向各遍历一次。
• 空间复杂度：O(N)，存储每步长度数组。

💻 代码

/**
 * 3614. Process String with Special Operations II
 */
function processStr(s: string, k: number): string {
  let len = 0n;
  const lens: bigint[] = [];

  // 记录每一步处理后的长度
  for (const ch of s) {
    if (ch >= 'a' && ch <= 'z') {
      len += 1n;
    } else if (ch === '*') {
      if (len > 0n) len -= 1n;
    } else if (ch === '#') {
      len *= 2n;
    } else if (ch === '%') {
      // 长度不变
    }

    lens.push(len);
  }

  let pos = BigInt(k);

  // 越界
  if (pos >= len) return '.';

  // 逆推
  for (let i = s.length - 1; i >= 0; i--) {
    const ch = s[i];

    const currLen = lens[i];
    const prevLen = i > 0 ? lens[i - 1] : 0n;

    if (ch >= 'a' && ch <= 'z') {
      // 当前字符新增的位置
      if (pos === prevLen) {
        return ch;
      }
    } else if (ch === '#') {
      // A -> AA
      if (prevLen > 0n) {
        pos %= prevLen;
      }
    } else if (ch === '%') {
      // reverse
      pos = prevLen - 1n - pos;
    } else if (ch === '*') {
      // 删除末尾字符
      // 对于仍然存在的位置，索引不变
    }
  }

  return '.';
}